import copy

minsupport = 2  # 最小支持度的频数


# 除去子集不是频繁项集的候选项集
def subset(sen_c_items, item):
    sub_set = []
    for i in sen_c_items:
        candidate = set(i)  # 将K-1项集中的候选项变成集合形式
        t_record = set(item)  # 将交易数据库中的数据项变成集合形式
        if candidate.issubset(t_record):
            sub_set.append(i)  # 保留子集部分
    return sub_set


# 找出K项候选集
def apriori_gen(sub_k_items, n):
    sen_k_items = set([])
    for p in range(len(sub_k_items)):
        for q in range(p + 1, len(sub_k_items)):
            flag = True
            p_item = list(sub_k_items[p])
            q_item = list(sub_k_items[q])
            for i in range(n):
                if p_item[n - 1] == q_item[n - 1]:
                    flag = False
                    break
                elif p_item[i] != q_item[i] and i < n-1:
                    flag = False
            if flag:
                c = list(sub_k_items[p] + q_item[n - 1])  # 将q中的最后一项添加到p中
                c.sort()
                if has_frequent_subset(c, sub_k_items, n):
                    c = "".join(c)
                    sen_k_items.add(c)
    print("候选", n + 1, "-项集：", sorted(sen_k_items))
    return sen_k_items


def has_frequent_subset(c, freq_items, n):
    num = len(c) * n
    count = 0
    flag = False
    for c_item in freq_items:
        if set(c_item).issubset(set(c)):
            count += n
    if count == num:
        flag = True
    return flag


# 剔除不频繁的项集
def op_freq_item(d):
    for item in list(d.keys()):
        if d[item] < minsupport:
            del d[item]
    l = sorted((d.keys()))
    return l


if __name__ == '__main__':
    dataset = ["ABCD", "BCE", "ABCE", "BDE", "ABCD", ]
    d = {}
    for t in dataset:  # 挑选频繁1项集
        for index in range(len(t)):
            if t[index] in d:
                d[t[index]] += 1
            else:
                d[t[index]] = 1
    l1 = op_freq_item(d)  # 剔除不符合的1项集
    sub_c_items = l1
    c_items_freq = {}  # 用于存放K-1候选项集，并统计其出现的频数
    freq_items = [sub_c_items]  # 保存频繁项集
    n = 0
    while True:
        n += 1
        print("寻找", n + 1, "-候选项集")
        sen_c_items = list(apriori_gen(sub_c_items, n))  # 找到K项集 sen_c_items
        for t in dataset:
            k_subset = sorted(subset(sen_c_items, t))  # 获取K项集包含候选项集的item的子集 new_c_item
            print(t, "的子集：", k_subset)
            for c_item in k_subset:
                if c_item in sen_c_items and c_item in c_items_freq:
                    c_items_freq[c_item] += 1  # 找到了加1
                else:
                    c_items_freq[c_item] = 1  # 未找到则创建并初始数量为1
        print("待挑选的频繁：", c_items_freq)
        if len(op_freq_item(c_items_freq)):
            sub_c_items = op_freq_item(c_items_freq)  # 选出K-1候选项集
            freq_items.append(sub_c_items)  # 将频繁K项集加入频繁项集freq_items中
            print(sub_c_items)
        else:
            break
        c_items_freq.clear()  # 清楚字典里的元素
        print()
    print("频繁项集：", freq_items)
